package 典型.动态规划;

public class BagComplete {
    public static Integer completePack(int V,int N,int[] weight,int[] value){
        int[][] dp = new int[N+1][V+1];
        for(int i=1;i<N+1;i++){
            for(int j=1;j<V+1;j++){
                if(weight[i-1] > j) dp[i][j] = dp[i-1][j];
                // 与01背包只是把dp[i-1]改成了dp[i]，在判断的时候，可能前一个已经放入一遍这个位置 。
                else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-weight[i-1]]+value[i-1]);
            }
        }
        //则容量为V的背包能够装入物品的最大值为
        return dp[N][V];
    }


    public static int completePack2(int V,int N,int[] weight,int[] value){
        //动态规划
        int[] dp = new int[V+1];
        for(int i=1;i<N+1;i++){
            //顺序实现，重复访问某个背包
            for(int j=weight[i-1];j<V+1;j++){
                dp[j] = Math.max(dp[j-weight[i-1]]+value[i-1],dp[j]);
            }
        }
        return dp[V];
    }
}
